package com.zyk.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangsan
 * @date 2021/4/9 13:07
 */
public class M0401 {

    // https://leetcode-cn.com/problems/route-between-nodes-lcci/
    public static boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        boolean[] visited = new boolean[n];
        return dfsFind(graph, visited, start, target);
    }

    public static boolean dfsFind(int[][] graph, boolean[] visited, int cur, int target) {
        if (visited[cur]) {
            return cur == target;
        }
        visited[cur] = true;
        for (int[] node : graph) {
            if (node[0] == cur) {
                if(node[1] == target) return true;
                if (dfsFind(graph, visited, node[1], target)) return true;
            }
        }
        return false;
    }

    /** 反向找start, 可以减少很多分支 */
    public static boolean findWhetherExistsPath2(int n, int[][] graph, int start, int target) {
        if(start == target) {
            return true;
        }
        for (int[] node : graph) {
            if(node[1] == target) {
                return findWhetherExistsPath(n, graph, start, node[0]);
            }
        }
        return false;
    }

    // for test
    public static void main(String[] args) {
        /*int n = 3;
        int[][] graph = {{0, 1}, {0, 2}, {1, 2}, {1, 2}};
        int start = 0, target = 2;*/
        int n = 25;
        int[][] graph = {{0, 1}, {0, 3}, {0, 10}, {0, 18}, {1, 2}, {1, 7}, {1, 11}, {1, 12}, {2, 4}, {2, 5}, {
                2, 13}, {2, 16}, {3, 6}, {3, 8}, {4, 9}, {5, 17}, {7, 20}, {7, 22}, {8, 10}, {10, 19}, {11, 15}, {13, 14}, {
                14, 21}, {15, 23}, {19, 24}, {20, 22}};
        int start = 0, target = 12;
        /*int n = 5;
        int[][] graph = {{0, 1}, {0, 2}, {0, 4}, {0, 4}, {0, 1}, {1, 3}, {1, 4}, {1, 3}, {2, 3}, {3, 4}};
        int start = 0, target = 4;*/

        System.out.println(findWhetherExistsPath(n, graph, start, target));
        System.out.println(findWhetherExistsPath2(n, graph, start, target));

//        bfs(n, graph);
//        dfs(n, graph);
    }

    // for test
    public static void bfs(int n, int[][] graph) {
        // 宽度优先遍历
        System.out.println("bfs(宽度优先遍历): ");
        Queue<Integer> queue = new LinkedList<>();
        queue.add(graph[0][0]);
        boolean[] visited = new boolean[n];
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (visited[cur]) {
                continue;
            }
            System.out.print(cur + " ");
            for (int[] node : graph) {
                if (node[0] == cur) {
                    queue.add(node[1]);
                }
            }
            visited[cur] = true;
        }

        System.out.println();
    }

    // for test
    public static void dfs(int n, int[][] graph) {
        System.out.println("dfs(深度优先遍历): ");
        boolean[] visited = new boolean[n];
        dfsProcess(graph, visited, graph[0][0]);

        System.out.println();
    }

    private static void dfsProcess(int[][] graph, boolean[] visited, int cur) {
        if (visited[cur]) {
            return;
        }
        System.out.print(cur + " ");
        visited[cur] = true;
        for (int[] node : graph) {
            if (node[0] == cur) {
                dfsProcess(graph, visited, node[1]);
            }
        }
    }

}
